import java.util.Iterator;
import java.util.Arrays;

public class RandomQueue<Item> implements Iterable<Item> {

	private Item[] arr;
	private int N; //Number of elements, and the index for the next insertion
	
	public RandomQueue() {
		arr = (Item[]) new Object[1];
		this.N = 0;
	}
	
	public boolean isEmpty () {
		return this.N == 0;
	}
	
	public int size() {
		return this.N;
	}
	
	//return a random item	
	public Item sample() {
		check(); //check, and maybe throw exception
		int r = StdRandom.uniform(this.N);
		return arr[r];
	}
	
	//return an iterator over the item in random order
	public Iterator<Item> iterator() {
		return new It();
	}
	
	private class It implements Iterator<Item> {
		private int curr = 0;
		private Item[] order;

		public boolean hasNext () {
			return curr < N;
		}
		
		public Item next() {
			return order[curr++];
		}
			
		public void remove() {
		//Cold weather makes people stupid and that's a fact (1993)
		}
	
		public It() {
			order = (Item[]) new Object[N];
			for (int i =0; i<N; i++) {
				order[i] = arr[i];
			}

			for (int i =0; i<N;i++) { //@Andreas: Ville det i grunden ikke være tilstrækkeligt med N/2?
				swap(StdRandom.uniform(N),StdRandom.uniform(N));
			}
		}
		
		private void swap(int p, int q) {
			if (p==q) return;
			Item tmp = order[p];
			order[p] = order[q];
			order[q] = tmp;
		}
	}
	
	private void check() {
		if (isEmpty()) throw new RuntimeException("You're a noob\n There is is only so much you can do with empty lists :)");
	}

	private void resize(int newLength)	{
		Item[] tmp = (Item[]) new Object[newLength];
		for (int i=0; i<N; i++){
			tmp[i]=arr[i];
		}
		arr=tmp;
	}
	public void enqueue(Item item) {
		if (N == arr.length) resize(2*N);
		arr[N++] = item;
	}

	public Item dequeue() {
		check(); //check, and maybe throw exception
		int r = StdRandom.uniform(this.N);
		Item item = arr[r];
		arr[r] = arr[--N];
		arr[N] = null;
		if (N>0 && N == arr.length/4) resize (arr.length/2);
		return item;
	}


   public static void main(String args[])
  {
    // Build a queue containing the Integers 1,2,...,6:
    RandomQueue<Integer> Q= new RandomQueue<Integer>();
    for (int i = 1; i < 7; ++i) Q.enqueue(i); // autoboxing! cool!
 
    // Print 30 die rolls to standard output
    StdOut.print("Some die rolls: ");
    for (int i = 1; i < 30; ++i) StdOut.print(Q.sample() +" ");
    StdOut.println();

    // Let's be more serious: do they really behave like die rolls?
    int[] rolls= new int [10000];
    for (int i = 0; i < 10000; ++i)
      rolls[i] = Q.sample(); // autounboxing! Also cool!
    StdOut.printf("Mean (should be around 3.5): %5.4f\n", StdStats.mean(rolls));
    StdOut.printf("Standard deviation (should be around 1.7): %5.4f\n",
		  StdStats.stddev(rolls));
    
    // Let's look at the iterator. First, we make a queue of colours:
    
    RandomQueue<String> C= new RandomQueue<String>();
    C.enqueue("red"); C.enqueue("blue"); C.enqueue("green"); C.enqueue("yellow"); 

    Iterator I= C.iterator();
    Iterator J= C.iterator();

    StdOut.print("Two colours from first shuffle: ");
    StdOut.print(I.next()+" ");
    StdOut.print(I.next()+" ");
    
    StdOut.print("\nEntire second shuffle: ");
    while (J.hasNext()) StdOut.print(J.next()+" ");

    StdOut.print("\nRemaining two colours from first shuffle: ");
    StdOut.print(I.next()+" ");
    StdOut.println(I.next());
  }

}
